"""
给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
class Solution:
    def minimumTotal(self, triangle: [[int]]) -> int:
        n = len(triangle)
        # f[i][j]表示从三角形顶部走到三角形(i,j)位置的最小路径和
        f = [[0] * n for _ in range(n)]
        f[0][0] = triangle[0][0]
        for i in range(1, n):
            # f[i][0](第i层最左边)只能由上一层的第0个(i-1层最左边)走到
            f[i][0] = f[i - 1][0] + triangle[i][0]
            for j in range(1, i):
                f[i][j] = triangle[i][j] + min(f[i-1][j], f[i-1][j-1])
            # f[i][i](第i层最后一个)只能由上一层的最后一个(i-1)走到, 第i-1层只有i个, 坐标从0开始，所以i-1层最后一个坐标就是(i-1, i-1)
            f[i][i] = triangle[i][i] + f[i-1][i-1]
        # 返回的就是f[n-1][0]~f[n-1][n-1]的最小值
        return min(f[n - 1])

